import java.util.HashMap;

public class LRUCache {

    HashMap<Integer,Node> map;
    int useSized; //使用空间
    int capacity; //容量

    //两个辅助结点，便于插入和删除操作
    Node head;
    Node tail;

    static class Node {
        int key;
        int val;

        Node prev;
        Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }

        public Node() {}
    }

    //提供构造方法
    public LRUCache() {
        capacity = 3;
        map = new HashMap<>();
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
    }

    //插入
    public void put(int key, int val) {
        Node node = get(key);
        Node newNode = new Node(key,val);
        if(node == null) {
            //如果不存在这个结点，需要插入到尾巴
            if(useSized == capacity) {
                //需要进行删除
                removeFrontNode();
                //插入
                insertToTail(newNode);
            } else {
                //插入
                insertToTail(newNode);
                useSized++;
            }
        } else {
            //如果存在这个结点，需要进行更新操作，并且最后要将结点插入到尾巴
            removeNode(node);
            insertToTail(newNode);
        }
    }

    public boolean remove(int key) {
        Node node = get(key);
        if(node == null) {
            return false;
        }
        removeNode(node);
        return true;
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        map.remove(node.key);
    }

    private void insertToTail(Node node) {
        Node prev = tail.prev;
        tail.prev = node;
        node.next = tail;
        node.prev = prev;
        prev.next = node;
        map.put(node.key,node);
    }

    private void removeFrontNode() {
        Node del = head.next;
        head.next = del.next;
        del.next.prev = head;
        map.remove(del.key);
    }

    //查找
    public Node get(int key) {
        return map.get(key);
    }
}
